A system is said to provide differential privacy if the presence or absence of a particular record or value cannot be determined based on an output of the system, or can only be determined with a very low probability. For example, in the case of a website that allows users to rate movies, a curious user may attempt to make inferences about the movies a particular user has rated by creating multiple accounts, repeatedly changing the movie ratings submitted, and observing the changes to the movies that are recommended by the system. Such a system may not provide differential privacy because the presence or absence of a rating by a user (i.e., a record) may be inferred from the movies that are recommended (i.e., output).
Typically, systems provide differential privacy by introducing some amount of noise to the data or to the results of operations or queries performed on the data. While the addition of noise to the results of operations may not be problematic for systems such as the rating system described above, for some systems such noise may be problematic. For example, in a system of medical records that provides differential privacy, users may want a probability distribution of the noise that is added to the results.